#include <iostream>
#include <cmath>
#include <vector>
#include <fstream>
#include "BiGraph.h"

using namespace std;

void readGraph(int& n, BiGraph<int>& Gr, BiGraph<int>& log_Gr){
    ifstream input("in.txt", ifstream::in);
    if (!input.is_open()) { cout<<"No input file!\n"; exit(1); }
    
    input>>n; 
    
    double r;
    for(int j=0;j<n;++j){ 
        for(int i=0;i<n;++i){
            input>>r;
            if (r!=0) {
                Gr.add_edge(i+1,j+1,r);  // Èñõîäíûé ãðàô îáìåíà âàëþò
                log_Gr.add_edge(i+1,j+1,-log(r)); // Ãðàô ñ âåñîì -log îò ðåàëüíîãî êóðñà îáìåíà
            }
        }  
    }
    input.close();
}

int main(){
    BiGraph<int> BG;
    BiGraph<int> log_BG;
    int n;
    
    readGraph(n,BG, log_BG);
 
    for(int j=0;j<n;++j){ log_BG.add_edge(0,j+1,0); }
    /*Äîáàâëÿåì ôèêòèâíóþ âåðøèíó ñ ðåáðàìè ñ íóëåâîé ñòîèìîñòüþ äî îñòàëüíûõ âåðøèí,
    ÷òî áû íàéòè õîòü îäèí îòðèöàòåëüíûé öèêë, òàêèì îáðàçîì, åñëè ñóùåñòâóåò ïóòü îáìåíà 
    êàêîé-ëèáî âàëþòû ñ âûãîäîé, òî ìû åãî íàéäåì, à íóëåâàÿ âåðøèíà ãàðàíòèðîâàííî íå âîéäåò â íåãî,
    òàê êàê â íå¸ íå âõîäèò íè îäíî ðåáðî*/
    
    BiGraph<int>::Vertex* u = log_BG.Bellman_Ford( log_BG.get_vertex(0) ); 
    //åñëè åñòü îòðèöàòåëüíûé öèêë, ïîëó÷èì âåðøèíó, âõîäÿùóþ â íåãî, èíà÷å - Null
    
    BiGraph<int>::Vertex* v = u;
    
    cout<<"Exchange path:"<<endl;
    if ( u!=0 ){ 
       vector<int> path;
       for(; ; u=u->parent) {  // èäåì ïî ïðåäêàì âåðøèíû, âõîäÿùåé â îòðèöàòåëüíûé öèêë, ïîêà íå âåðíåìñÿ â íå¸
           path.push_back(u->get_name());
           if(u == v && path.size() > 1) { break; }
       }
       reverse(path.begin(), path.end());
       for(size_t k=0; k<path.size(); ++k) { 
           cout<<path[k]; 
           if (k<path.size()-1) {cout<<" -> ";}
       }
       cout<<endl;
       double benefit=1;
       for(size_t k=0; k < path.size()-1; ++k) { benefit*=BG.get_edge(path[k],path[k+1])->get_weight(); } // Ñ÷èòàåì âûãîäó ïî èçíà÷àëüíîìó îáìåííîìó ãðàôó
       cout<<"Benefit = "<<benefit*100<<"%"<<endl;
    } else { cout<<"No\n"; }
    
    cout<<endl;
    system("pause");
    return 0;
}
